//最小栈
class MinStack {
    vector<int> stack;
    vector<int> min_s;

public:
    MinStack() {}

    void push(int val) {
        stack.push_back(val);
        if (min_s.empty() || min_s.back() >= val) {
            min_s.push_back(val);
        }
    }

    void pop() {
        int t = stack.back();
        stack.pop_back();
        if (min_s.size() && min_s.back() == t) {
            min_s.pop_back();
        }
    }

    int top() { return stack.back(); }

    int getMin() { return min_s.back(); }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

 //N 皇后
class Solution {
    vector<vector<string>> ret;
    vector<string> path;
    int count = 0;
    bool col[10];
    bool dig1[18];
    bool dig2[18];

public:
    vector<vector<string>> solveNQueens(int n) {
        for (int i = 0; i < n; i++) {
            path.push_back(string(n, '.'));
        }
        dfs(n, 0);
        return ret;
    }
    void dfs(int n, int h) {
        if (count == n) {
            ret.push_back(path);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!col[i] && !dig1[h - i + n] && !dig2[h + i]) {
                dig1[h - i + n] = true;
                dig2[h + i] = true;
                col[i] = true;
                path[h][i] = 'Q';
                count++;
                dfs(n, h + 1);
                path[h][i] = '.';
                dig1[h - i + n] = false;
                dig2[h + i] = false;
                col[i] = false;
                count--;
            }
        }
    }
};